package realQuestion.nenglian;

public class Main2 {

    public boolean exist (String[] board, String word) {
        // write code here
        int x= board.length;
        int y = board[0].length();
        char[][] boards=new char[x][y];
        for (int i = 0; i < x; i++) {
            boards[i]=board[i].toCharArray();
        }
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                boolean dfs = dfs(boards, word.toCharArray(), i, j, 0, x, y);
                if (dfs){
                    return  true;
                }
            }
        }
        return  false;
    }
    public  boolean dfs(char[][] boards,char[]word,int i,int j,int k,int x,int y){
        if (i>x||j>y||k> word.length||boards[i][j]!= word[k]){
            return   false;
        }
        boolean res;
        boards[i][j]='0';
        res=dfs(boards,word,i-1,j,k+1,x,y)||
                dfs(boards,word,i+1,j,k+1,x,y)||
                dfs(boards,word,i,j-1,k+1,x,y)||
                dfs(boards,word,i,j+1,k+1,x,y);
        boards[i][j]=word[k];
        return  res;



    }

}


 class Main3 {

    public boolean exist (String[] board, String word) {
        // write code here
        int x= board.length;
        int y = board[0].length();
        char[][] boards=new char[x][y];
        for (int i = 0; i < x; i++) {
            boards[i]=board[i].toCharArray();
        }
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                boolean dfs = dfs(boards, word.toCharArray(), i, j, 0, x, y);
                if (dfs){
                    return  true;
                }
            }
        }
        return  false;
    }
    public  boolean dfs(char[][] boards,char[]word,int i,int j,int k,int x,int y){
        if (i>x||j>y||k> word.length||boards[i][j]!= word[k]){
            return   false;
        }
        boolean res;
        boards[i][j]='0';
        res=dfs(boards,word,i-1,j,k+1,x,y)||
                dfs(boards,word,i+1,j,k+1,x,y)||
                dfs(boards,word,i,j-1,k+1,x,y)||
                dfs(boards,word,i,j+1,k+1,x,y);
        boards[i][j]=word[k];
        return  res;



    }

}

